🗓️ 구간 스케줄링 문제 (회의실 배정)

여러 회의 시간이 주어질 때, 겹치지 않게 진행할 수 있는 최대 회의 개수를 구하는 대표적인 그리디 문제입니다.

1️⃣ 문제 접근

• 시작 시간이 아니라 종료 시간이 빠른 순서로 정렬하는 것이 핵심
• 종료 시간이 빠른 회의부터 선택하면, 다음 회의를 선택할 수 있는 여유 시간이 가장 많이 남음
• 마지막으로 선택한 회의의 종료 시간보다 시작 시간이 늦거나 같은 회의만 다음 후보로 고려

2️⃣ 풀이 코드

function maxMeetings(meetings) {
  const sorted = [...meetings].sort((a, b) => a.end - b.end);
  let count = 0, lastEnd = -Infinity;

  for (const { start, end } of sorted) {
    if (start >= lastEnd) {
      count++;
      lastEnd = end;
    }
  }

  return count;
}

maxMeetings([{ start: 1, end: 3 }, { start: 2, end: 5 }, { start: 4, end: 6 }]); // 2

✍️ 한 줄 정리

회의실 배정 문제는 시작 시간이 아니라 종료 시간 기준으로 정렬해 그리디하게 선택해야 최대 개수를 보장할 수 있다.